/**
 * 简单堆排序实现
 */
public class SimpleHeapSort {

    // 将输入的数组元素从小到大排序
    public void sort(int[] nums) {
        // 第一步，原地建堆，注意这里建的是大顶堆
        // 只要从左到右对每个元素调用swim方法，就可以原地建堆
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            maxHeapSwim(nums, i);
        }

        // 第二步， 排序，现在整个数组已经是一个大顶堆了，直接模拟删除堆顶元素的过程即可
        int heapSize = n;
        while (heapSize > 0) {
            // 从堆顶删除元素，放到堆的后面
            swap(nums, 0, heapSize - 1);
            heapSize--;
            // 恢复堆的性质
            maxHeapSink(nums, 0, heapSize);
            // 现在nums[0...heapSize)是一个大顶堆，nums[heapSize...)是有序元素

        }
    }

    // 大顶堆的上浮操作
    void maxHeapSwim(int[] heap, int node) {
        while (node > 0 && heap[parent(node)] < heap[node]) {
            swap(heap, parent(node), node);
            node = parent(node);
        }
    }

    // 大顶堆的下沉操作
    void maxHeapSink(int[] heap, int node, int size) {
        while (left(node) < size || right(node) < size) {
            // 小顶堆和大顶堆的唯一区别就在这里，比较逻辑相反
            // 比较自己和左右子节点，看看谁最大
            int max = node;
            if (left(node) < size && heap[left(node)] > heap[max]) {
                max = left(node);
            }
            if (right(node) < size && heap[right(node)] > heap[max]) {
                max = right(node);
            }
            if (max == node) {
                break;
            }
            swap(heap, node, max);
            node = max;
        }
    }


    // 父节点的索引
    int parent(int node) {
        return (node - 1) / 2;
    }

    // 左子节点的索引
    int left(int node) {
        return node * 2 + 1;
    }

    // 右子节点的索引
    int right(int node) {
        return node * 2 + 2;
    }

    // 交换数组中两个元素的位置
    void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}
